/** Objekt tokenu. */
class Token implements Cloneable {

	/* Vlajky tokenu. TF = Token Flag. */

	/** Vlajka tokenu "nic". */
	public static final int TF_NONE = 0;
	/** Vlajka tokenu "zacina radek". */
	public static final int TF_BEGINS_LINE = (1 << 0);
	/** Vlajka tokenu "ukoncuje radek". */
	public static final int TF_ENDS_LINE = (1 << 1);
	/** Vlajka tokenu "povoleny upravy casu rezervovanych slov". */
	public static final int TF_RESERVED_WORDS_ON = (1 << 2);
	/** Vlajka tokenu "povoleny upravy casu direktiv". */
	public static final int TF_DIRECTIVES_ON = (1 << 3);
	/** Vlajka tokenu "povoleny upravy casu identifikatoru". */
	public static final int TF_IDENTIFIERS_ON = (1 << 4);
	/** Vlajka tokenu "povoleno vkladani mezer na vhodna mista". */
	public static final int TF_INSERT_SPACES_ON = (1 << 5);
	/** Vlajka tokenu "povoleno odsazovani". */
	public static final int TF_INDENT_ON = (1 << 6);
	/** Vlajka tokenu "povoleno zalamovani radku". */
	public static final int TF_WRAP_ON = (1 << 7);
	/** Vlajka tokenu "povoleno vkladani prazdnych radku". */
	public static final int TF_BLANK_LINES_ON = (1 << 8);

	public enum Klass {
		KLASS_WHITESPACE,
		KLASS_COMMENT,
		KLASS_VIRTUAL_ROUND_BRACKET,
		KLASS_RESERVED_WORD
	}

	public int flags;
	/** Radek, kde zacina (indexovano od 0). */
	public int row;
	/** Sloupec, kde zacina (indexovano od 0). */
	public int col;
	/** Odkaz na predchozi token ve spojaku. */
	public Token prev;
	/** Odkaz na nasledujici token ve spojaku. */
	public Token next;

	public String text;
	public Klass klass;

	/**
	 * Vytvori token podle zadanych parametru.
	 *
	 * @param text text
	 * @param klass trida
	 * @param flags vlajky
	 * @param row radek, kde zacina (indexovano od 0)
	 * @param col sloupec, kde zacina (indexovano od 0)
	 * @param prev odkaz na predchozi token ve spojaku
	 * @param next odkaz na nasledujici token ve spojaku
	 */
	public Token (
		String text,
		Klass klass,
		int flags,
		int row, int col,
		Token prev,
		Token next ) {

		this.text = text;
		this.klass = klass;
		this.flags = flags;
		this.row = row;
		this.col = col;
		this.prev = prev;
		this.next = next;
	}

	@Override
	public Object clone () {
		return new Token( text, klass, flags, row, col, null, null );
	}

	/**
	 * Odpovida token dane tride a textu?
	 *
	 * @param klass trida
	 * @param text text
	 * @return <code>true</code> pokud token odpovida dane tride a textu;
	 *         <code>false</code> pokud token neodpovida dane tride a textu
	 */
	boolean match ( Klass klass, String text ) {
		return ( this.klass == klass ) && this.text.equalsIgnoreCase( text );
	}
}

// ---------------------------------------------------------------------------

/** Zajistuje spravne odsazovani. */
public class Indent {

	/**
	 * Vrati <code>1</code> nebo <code>0</code> podle toho, jestli je dany druh
	 * odsazeni jen realny nebo virtualni.
	 *
	 * Vracena hodnota je ve volajici funkci pouzita jako koeficint, coz ma
	 * efektivne za nasledek, ze se virtualni druh odsazovani fyzicky
	 * neodsazuje.
	 *
	 * @param klass druh odsazeni
	 * @return <code>1</code> pokud je druh odsazeni realny;
	 *         <code>0</code> pokud je druh odsazeni virtualni
	 */
	private static int indentLevel ( Token.Klass klass ) {
		return ( klass == Token.Klass.KLASS_VIRTUAL_ROUND_BRACKET ) ? 0 : 1;
	}

	/**
	 * Trida popisujici jednu uroven odsazeni. Slouzi jako jedna polozka
	 * v zasobniku odsazeni.
	 */
	private static final class IndentLevel {
		/** Druh odsazeni. */
		public Token.Klass klass;
		/** Ukazatel na dalsi polozku zasobniku, */
		public IndentLevel next;

		IndentLevel ( Token.Klass klass ) {
			this.klass = klass;
		}
	}

	/** Trida popisujici aktualni stav odsazovani v prubehu algoritmu. */
	private final static class IndentContext {
		/** Zasobnik <code>Indent</code>u. */
		protected IndentLevel top;
		/** Aktualni uroven odsazeni. */
		protected int currLevel;
		/** Minimalni uroven odsazeni na teto radce. */
		protected int minLevel;
		/** Koeficient na skalovani odsazeni. */
		protected static final int indentScale = 4;

		/**
		 * Odebere polozku ze zasobniku <code>Indent</code>u.
		 *
		 * @return odebrana polozka
		 */
		protected IndentLevel pop () {
			if ( top == null ) {
				return null;
			}

			IndentLevel topLevel = top;
			top = top.next;
			currLevel -= indentScale * indentLevel( topLevel.klass );
			if ( minLevel > currLevel ) {
				minLevel = currLevel;
			}
			return topLevel;
		}

		/**
		 * Prida polozku na zasobnik <code>Indent</code>u.
		 *
		 * @param indent pridavana polozka
		 */
		protected void push ( IndentLevel indent ) {
			if ( top != null ) {
				indent.next = top;
			} else {
				indent.next = null;
			}
			top = indent;
			currLevel += indentScale * indentLevel( indent.klass );
		}

		/**
		 * Odsadi o jednu uroven, jejiz druh je urcen parametrem
		 * <code>klass</code>.
		 *
		 * @param klass druh odsazeni
		 */
		public void indent ( Token.Klass klass ) {
			IndentLevel odsazeni = new IndentLevel( klass );
			push( odsazeni );
		}

		/** Odsadi zpatky. */
		public void unindent () {
			pop();
		}

		/** Odsadi zpatky, ale nesnizi pritom <code>minLevel</code>. */
		public void unindentNext () {
			int minLevelTemp = minLevel;
			pop();
			minLevel = minLevelTemp;
		}

		/**
		 * Zjistuje, zda je druh odsazeni na vrcholu zasobniku
		 * <code>klass</code>.
		 *
		 * @param klass druh odsazeni, se kterym se porovnava druh odsazeni
		 * na vrcholu zasobniku
		 * @return <code>true</code> pokud je zasobnik neprazdny a druh odsazeni
		 * na jeho vrcholu je <code>klass</code>;
		 * <code>false</code> pokud je zasobnik prazdny nebo je druh odsazeni
		 * na jeho vrcholu jiny nez <code>klass</code>
		 */
		public boolean isAtTop ( Token.Klass klass ) {
			if ( top == null ) {
				return false;
			}

			return ( top.klass == klass );
		}
	};

	/**
	 * Preskoci bile mezery a komentare, ktere nasleduji za <code>start</code>.
	 *
	 * @param start token, za kterym se preskakuji bile mezery a komentare,
	 * sam to nemusi byt bily komentar nebo mezera
	 * @return nejblizsi token za <code>start</code>, ktery neni bila mezera
	 * ani komentar;
	 * <code>null</code> pokud takovy uz ve spojaku neni
	 */
	private static Token skipWhitespaceAndComments ( Token start ) {
		Token t = start.next;
		while ( t != null ) {
			if (
				t.klass != Token.Klass.KLASS_WHITESPACE &&
				t.klass != Token.Klass.KLASS_COMMENT ) {

				break;
			}

			t = t.next;
		}
		return t;
	}

	/**
	 * Preskoci vsechny tokeny od <code>token</code> (vcetne) a nemaji tridu
	 * <code>klass</code> a text <code>text</code>.
	 *
	 * @param token token, za kterym se preskakuji neodpovidajici tokeny
	 * @param klass trida hledaneho tokenu
	 * @param text text hledaneho tokenu
	 * @return nejblizsi token za <code>token</code> (vcetne) se tridou
	 * <code>klass</code> a textem <code>text</code>; <code>null</code> pokud
	 * takovy uz ve spojaku neni
	 */
	private static Token skipUntil (
		Token token,
		Token.Klass klass,
		String text ) {

		Token t = token;
		while ( t != null ) {
			if ( t.klass == klass && t.text.equalsIgnoreCase( text ) ) {
				break;
			}

			t = t.next;
		}
		return t;
	}

	/**
	 * Zmeni hodnotu polozky <code>col</code> o <code>delta</code> u vsech
	 * tokenu od  <code>start</code> az do konce radku.
	 *
	 * @param start prvni token, kde se ma menit hodnota <code>col</code>
	 * @param delta o kolik se ma zmenit hodnota <code>col</code>
	 */
	private static void changeColUntilEOL ( Token start, int delta ) {
		Token token = start;
		while ( token != null ) {
			if ( token.row != start.row ) {
				break;
			}

			token.col += delta;
			token = token.next;
		}
	}

	/**
	 * Zmeni hodnotu polozky <code>row</code> o <code>delta</code> u vsech
	 * tokenu od <code>start</code> az do konce spojaku tokenu.
	 *
	 * @param start prvni token, kde se ma menit hodnota <code>row</code>
	 * @param delta o kolik se ma zmenit hodnota <code>row</code>
	 */
	private static void changeRowUntilEOF ( int delta, Token start ) {
		Token token = start;
		while ( token != null ) {
			token.row += delta;
			token = token.next;
		}
	}

	/**
	 * Vraci true, pokud dany token zacina radku.
	 */
	private static boolean beginsLine ( Token token ) {
		return
			( ( token.flags & Token.TF_BEGINS_LINE ) != Token.TF_BEGINS_LINE );
	}

	/**
	 * Vraci true, pokud dany token konci radku.
	 */
	private static boolean endsLine ( Token token ) {
		return ( ( token.flags & Token.TF_ENDS_LINE ) != Token.TF_ENDS_LINE );
	}

	/**
	 * Zaridi, aby za danym tokenem byl prazdny radek.
	 *
	 * @param token token, za kterym ma byt prazdna radka
	 */
	private static void ensureBlankLineAfter ( Token token ) {
		if ( token == null || token.next == null ) {
			return;
		}

		// najdi posledni token na radce
		while ( token != null && !endsLine( token ) ) {
			token = token.next;
		}

		// zkontroluj zda existuje
		if ( token == null || token.next == null ) {
			return;
		}
		if ( endsLine( token.next ) ) {
			return;
		}

		changeRowUntilEOF( 1, token.next );

		// vloz token reprezentujici prazdnou radku
		Token newLineToken = new Token(
			"\n", Token.Klass.KLASS_WHITESPACE,
			token.next.flags | Token.TF_BEGINS_LINE | Token.TF_ENDS_LINE,
			token.next.row, 0,
			token, token.next );
		token.next.prev = newLineToken;
		token.next = newLineToken;
	}

	/**
	 * Vytvori string odsazeni (slozeny z mezer) dane delky.
	 */
	private static String createIndent ( int level ) {
		String text = "";
		for ( int i = 1; i <= level; i++ ) {
			text += ' ';
		}
		return text;
	}

	/**
	 * Odsadi radek zacinajici tokenem <code>start</code> na uroven
	 * <code>level</code>.
	 *
	 * @param start prvni token na radce
	 * @param level uroven, na kterou ma byt tato radka odsazena
	 * @return token, kterym radka zacina po odsazeni (neni nutne stejny
	 * jako <code>start</code>)
	 */
	private static Token indentLine ( Token start, int level ) {
		Token result = start;
		if ( start.klass == Token.Klass.KLASS_WHITESPACE ) {

			if ( start.text.length() == level ) {
				// mame pozadovane odsazeni
				return start;
			}

			if ( !endsLine( start ) ) {
				// uprav existujici token na dane odsazeni
				if ( level > 0 ) {
					int delta = level - start.text.length();
					start.text = createIndent( level );
					changeColUntilEOL( start.next, delta );
				} else {

					if ( start.prev != null ) {
						start.prev.next = start.next;
					}
					if ( start.next != null ) {
						start.next.prev = start.prev;
					}
					start.next.flags |= Token.TF_BEGINS_LINE;

					int delta = -(int)start.text.length();
					changeColUntilEOL( start.next, delta );
					result = start.next;
				}
			}
		} else if ( level > 0 ) {
			changeColUntilEOL( start, level );

			// vytvor novy token reprezentujici odsazeni
			String text = createIndent( level );
			Token newToken = new Token(
				text, Token.Klass.KLASS_WHITESPACE,
				( start.flags & ~Token.TF_ENDS_LINE ) | Token.TF_BEGINS_LINE,
				start.row, start.col,
				start.prev, start );

			// pridej ho
			if ( start.prev != null ) {
				start.prev.next = newToken;
			}
			start.prev = newToken;
			start.flags &= ~Token.TF_BEGINS_LINE;
		}

		return result;
	}

	/**
	 * Vrati true, pokud je token na radce sam.
	 */
	private static boolean isStandalone ( Token token ) {
		if ( !beginsLine( token ) ) {
			Token t = token.prev;
			while ( t != null ) {
				if ( t.klass != Token.Klass.KLASS_WHITESPACE ) {
					return false;
				} else if ( beginsLine( token ) ) {
					return true;
				}

				t = t.prev;
			}
		}
		return true;
	}

	/**
	 * Vrati token zacinajici radku, na ktere lezi i token predany parametrem.
	 */
	private static Token getFirstTokenOnLine ( Token token ) {
		Token t = token;
		while ( t != null ) {
			if ( beginsLine( token ) ) {
				return t;
			}

			t = t.prev;
		}
		return null;
	}

	/**
	 * Odsadi urcite typy komentaru podle toho, k cemu patri.
	 *
	 * @param tokens spojovy seznam tokenu, kde se maji najit
	 * a odsadit komentare
	 */
	private static void indentComments ( Token tokens ) {

		for ( Token token = tokens; token != null; token = token.next ) {

			// zajima nas tento token?
			if ( token.klass != Token.Klass.KLASS_COMMENT ) {
				continue;
			}
			if ( !isStandalone( token ) ) {
				continue;
			}

			// najdeme textovy token, ke kteremu se komentar vztahuje
			Token nextTextToken = token.next;
			while ( nextTextToken != null ) {
				if (
					nextTextToken.klass != Token.Klass.KLASS_COMMENT &&
					nextTextToken.klass != Token.Klass.KLASS_WHITESPACE ) {

					break;
				}

				nextTextToken = nextTextToken.next;
			}

			// existuje takovy vubec?
			boolean isReservedWord =
				nextTextToken.match( Token.Klass.KLASS_RESERVED_WORD, "end" ) ||
				nextTextToken.match( Token.Klass.KLASS_RESERVED_WORD, "until" );
			if ( nextTextToken == null || isReservedWord ) {
				continue;
			}

			// odsadime radku
			Token first = getFirstTokenOnLine( token );
			if ( first != null ) {
				indentLine( first, nextTextToken.col );
			} else {
				// zde by mel byt ASSERT
			}
		}
	}

}